package GraphCut;
import java.util.Arrays;
import java.util.LinkedList;
import ij.IJ;
import ij.ImagePlus;
import ij.process.ImageProcessor;
public class Graph
{
	private boolean simpleWeights;
	private int maxI; //maksymalna wartosc na histogramie
	private int minI; //minimalna wartosc na histogrami
	private int K;
	private int n; //szerokosc
	private int m; //wysokosc
	private int avgObj; //srednia intensywnosc pikseli dla obiektu
	private int avgBack; //j.w. dla tla
	private int ro;
	private int lambda;
	private int objectPixelCount;
	private int backgroundPixelCount;
	private int [] nodes; //tablica zawierajaca intensywnosci pikseli(z macierzy pikseli robiona jest jedna dluga tablica, troche latwiej ogarnac)
	private byte [] terminals; //tablica oznaczajaca przynaleznosc piksela do konkretnej grupy(czyli do zrodla, zlewu, albo brak przynaleznosci)
	private Edge [][] edges; //tablica list z krawedziami
	final static public byte SOURCE = 0;
	final static public byte SINK = 1;
	final static public byte NONE = 2;
	private int [] objectHistogram;
	private int [] backgroundHistogram;
	private int [] index;
	/*n-ilosc wierzcholkow*/
	// 0 - wierzcholek S
	// n*m+1 - wierzcholek T
	@SuppressWarnings("unchecked")
	public Graph(int n, int m, ImageProcessor imp)
	{
		simpleWeights = true;
		this.n = n;
		this.m = m;
		nodes = new int[n*m+2];
		terminals = new byte[n*m];
		edges = new Edge[n*m+2][];
		nodes[0] = SOURCE; //pierwszy wierzcholek grafu to zrodlo(ta informacja nie jest wykorzystywana do niczego)
		nodes[n*m+1] = SINK; //ostatni to ujscie
		Arrays.fill(terminals, Graph.NONE);
		/*pobranie intensywnosci pikseli*/	
		for(int i = 0; i <n; ++i)
		{
			for(int j = 0; j<m;++j)
				nodes[i+j*n+1] = (int)imp.getPixelValue(i,j);
		}
		edges[0] = new Edge[n*m];
		edges[n*m+1] = new Edge[n*m];
		for(int i = 1; i<n*m+1;i++)
		{
			edges[i] = new Edge[6];
		}
		for(Edge[] k: edges)
		{
			Arrays.fill(k, null);
		}
		index = new int[nodes.length];
		Arrays.fill(index, 0);
	}
	
public void setNodeTerminal(int p, byte terminal)
{
	terminals[p] = terminal;
}

public void setEdges()
{
	setNLinks();
	setTLinks();
}

/* ustawiamy tLinki, czyli do zrodla i zlewu, dodane takze krawedzie zwrotne o pojemnosci 0)
 * DZIALA DOBRZE
 */
private void setTLinks()
{
	for(int i = 0; i<nodes.length-2 ;i++)
	{
		if(terminals[i] == NONE){
			edges[0][index[0]++] =new Edge(sWeight(nodes[i+1]), i+1);
			edges[i+1][index[i+1]++]=new Edge(tWeight(nodes[i+1]), nodes.length-1);
			edges[i+1][index[i+1]++]=new Edge(0,0);
			edges[nodes.length-1][index[nodes.length-1]]=new Edge(0,i+1);
		}
		else if(terminals[i] == SOURCE)
		{
			edges[0][index[0]++] =new Edge(K, i+1);
			edges[i+1][index[i+1]++]=new Edge(0, nodes.length-1);
			edges[i+1][index[i+1]++]=new Edge(0,0);
			edges[nodes.length-1][index[nodes.length-1]]=new Edge(0,i+1);
		}
		else if(terminals[i] == SINK)
		{
			edges[0][index[0]++]=new Edge(0, i+1);
			edges[i+1][index[i+1]++]=new Edge(K, nodes.length-1);
			edges[i+1][index[i+1]++]=new Edge(0,0);
			edges[nodes.length-1][index[nodes.length-1]]=new Edge(0,i+1);
		}
	}
}

/*ustawiamy krawedzie miedzy wierzcholkami
 * DZIALA DOBRZE
 */
private void setNLinks()
{
	for(int i = 1;i<n*m+1;i++)
	{
			if(i%n>0)
			{
				edges[i][index[i]++]=new Edge(nWeight(nodes[i], nodes[i+1]),i+1);
				edges[i+1][index[i+1]++]=new Edge(nWeight(nodes[i], nodes[i+1]),i);
			}
			if(Math.ceil((double)i/n)!=m)
			{
				edges[i][index[i]++]=new Edge(nWeight(nodes[i],nodes[i+n]),i+n);
				edges[i+n][index[i+1]++]=new Edge(nWeight(nodes[i],nodes[i+n]),i);
			}	
	}
	int max = 0;
	for(int i=1;i<edges.length-2;i++)
	{
		int tmp =0;
		for(Edge k: edges[i])
		{
			if(k==null)
				break;
			tmp+=k.capacity;
		}
		if(tmp>max)
			max=tmp;
	}
	if(simpleWeights)
		K=Integer.MAX_VALUE;
	else
		K=1+max;
}


public long GraphCutDinic()
{
	int [] dist = new int[nodes.length];
	LinkedList<Integer> q = new LinkedList<Integer>();
	long flow = 0;
	int [] start = new int[nodes.length];
	while(Dinic_BFS(dist, q)){
		Arrays.fill(start,0);
		while(true){
			int df = Dinic_DFS(0, Integer.MAX_VALUE,start, dist);
			if(df==0)
				break;
			flow+=df;
		}
	}
	return flow;
}

private boolean Dinic_BFS(int [] dist, LinkedList<Integer> q)
{
	Arrays.fill(dist, -1);
	dist[0] = 0;
	q.clear();
	q.add(0);
	while(!q.isEmpty()){
		int u = q.pop();
		for (Edge e: edges[u]){
			if(e==null)
				break;
			if(e.flow < e.capacity && dist[e.toVertex]<0){
				dist[e.toVertex] = dist[u] +1;
				if(e.toVertex == nodes.length-1)
					return true;
				q.add(e.toVertex);
			}
		}
	}
	return false;
}
private int Dinic_DFS(int u, int f, int [] start, int[] dist)
{
	if(u == nodes.length - 1)
		return f;
	for(int i = start[u];i<index[u];start[u] = ++i){
		Edge e =(Edge) edges[u][i];
		if(e == null)
		{
			continue;
		}
		int v = e.toVertex;
		if(e.flow < e.capacity && dist[v] == dist[u]+1){
			int ff = Dinic_DFS(v, Math.min(f, e.capacity - e.flow), start,dist);
			if( ff> 0){
				e.flow += ff;
				for(Edge k: edges[e.toVertex])
				{
					if(k==null)
						break;
					if(k.toVertex == u)
						k.flow-=ff;
				}
				return ff;
			}
		}
	}
	
	return 0;
}

public byte[] getSegmentation()
{
	for(Edge e: edges[0])
	{
		if(e==null)
			break;
		if(simpleWeights)
		{
			if(e.capacity-e.flow==0)
				terminals[e.toVertex-1] = 0;
			else{
				terminals[e.toVertex-1] =(byte)255;
			}
		}
		else
		{
			if(terminals[e.toVertex-1]== Graph.SINK||(e.capacity-e.flow>0&&terminals[e.toVertex-1]!=Graph.SOURCE) )
				terminals[e.toVertex-1] = 0;
			else if(terminals[e.toVertex-1]== Graph.SOURCE || e.capacity-e.flow==0){
				terminals[e.toVertex-1] =(byte)255;
			}
		}
	}

	
	return terminals;
}

public void setMaxI(int k)
{
	maxI = k;
}
public void setMinI(int k)
{
	minI = k;
}
public void setAvgObj(int k)
{
	avgObj = k;
}

public void setAvgBack(int k)
{
	avgBack = k;
}
/*
 * Waga krawedzi miedzy pikselami
 */
public int nWeight(int p, int q)
{
	if(simpleWeights)
		return (maxI-minI) - Math.abs(p-q);
	else
		return (int) (lambda*Math.exp(-1*Math.pow(p-q,2)/Math.pow(ro,2)));
}

/*
 * Waga krawedzi miedzy zrodlem a pikselem
 */
public int sWeight(int p)
{
	if(simpleWeights)
		return (maxI - Math.abs(avgObj-p));
	else
		return (int)Math.ceil(lambda *(Math.log(objectPixelCount)-Math.log(objectHistogram[p])));
}

/*
 * Waga krawedzi miedzy pikselem a zlewem, wersja banalna
 */
public int tWeight(int p)
{
	if(simpleWeights)
		return maxI-Math.abs(avgBack -p);
	else
		return (int)Math.ceil(lambda *(Math.log(backgroundPixelCount)-Math.log(backgroundHistogram[p])));
}

public void setWeights(boolean isRo, int value)
{
	if(isRo)
		ro = value;
	else
		lambda = value;
}

public void setHistogram(int [] histogram, boolean object)
{
	int avg = 0;
	int pixelCount = 0;
	for(int i = 0; i<histogram.length; i++)
	{
		avg+=i*histogram[i];
		pixelCount+=histogram[i];
	}
	
	if(object)
	{
		objectHistogram = histogram;
		objectPixelCount = pixelCount;
		avgObj = avg/objectPixelCount;
	}
	else
	{
		backgroundHistogram = histogram;
		backgroundPixelCount = pixelCount;
		avgBack = avg/backgroundPixelCount;
	}
}

public void clearHistograms()
{
	clearHistogram(true);
	clearHistogram(false);
}

public void clearHistogram(boolean object)
{
	if(object)
	{
		objectHistogram = null;
		objectPixelCount = 0;
		avgObj = 0;
		for(Byte k: terminals)
		{
			if(k==Graph.SOURCE)
				k=Graph.NONE;
		}
	}
	else
	{
		backgroundHistogram = null;
		objectPixelCount = 0;
		avgBack = 0;
		for(Byte k: terminals)
		{
			if(k==Graph.SINK)
				k=Graph.NONE;
		}
	}
}

public void setSimpleWeights(boolean simple)
{
	simpleWeights = simple;
}

public void clear()
{
	Arrays.fill(terminals, Graph.NONE);
	for(Edge[] k: edges)
	{
		Arrays.fill(k, null);
	}
	Arrays.fill(index, 0);
}


}
